package main.leetcode.offer.firstround.from03to50;

import main.datastruc.TreeNode;

import java.util.ArrayList;
import java.util.List;

import static main.datastruc.TreeNode.creCmpBTree;

/**
 * 34.二叉树中和为某一值的路径
 *
 * <p>输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 *
 * <p>
 *
 * <p>提示：节点总数 <= 10000
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex34 {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode root = creCmpBTree(new int[] {-2, 99, -3});
        new ex34().pathSum(root, -5);
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) return res;
        list.add(root.val);
        if (root.val == sum && root.left == null && root.right == null) { // 达到终点
            res.add(new ArrayList<>(list));
        } else { // 但是左右子树还存在值为0的情况
            sum -= root.val;
            if (root.left != null) pathSum(root.left, sum);
            if (root.right != null) pathSum(root.right, sum);
        }
        list.remove(list.size() - 1); // 此节点已遍历，吐出，返回上一层给兄弟结点遍历
        return res;
    }
}
